#include <stdio.h>
#include <stdlib.h>
#include "LinkTree.h"
#include <string.h>

#define true 1
#define false 0

//初始化
int InitLTree(LTree* tree)
{
    struct UniversalType typedata = {NULL,-1};//初始化通用数据类型结构体，相当于置空
    tree->root = CreateTreeNode(typedata);//创建树根节点
    if(tree->root == NULL)
        return false;  
    else
        return true;
}

//创建树节点
LTNode* CreateTreeNode(ElementType element)
{
    LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));//申请树节点内存
    if(newNode == NULL)
    {
        printf("Create malloc error!\n");
        return NULL;
    }
    newNode->data = element;    //关联数据
    newNode->firstChild = NULL; //树孩子节点地址记录置空
    newNode->nextsibling = NULL;//树兄弟节点地址记录置空
    newNode->parent = NULL;     //树父节点地址记录置空
    return newNode;
}

//链接
void ConnectBranch(LTNode* parent, LTNode* child)
{
    if(parent == NULL || child == NULL)
        return;                             //相当于单向链表的头插，
    child->nextsibling = parent->firstChild;//child兄弟节点指针指向parent孩子节点
    parent->firstChild = child;             //parent孩子节点指针指向child
    child->parent = parent;                 //child父节点指针指向parent
}

//断开
void DisconnectBranch(LTNode* parent, LTNode* child)
{
    if(parent == NULL || child == NULL || parent->firstChild == NULL)
        return;
    LTNode* cur = parent->firstChild;//创建临时节点记录指针cur，指向parent的孩子节点
    if(cur == child)//若parent->firstChild == child
    {
        parent->firstChild = cur->nextsibling;//parent孩子节点指针指向child的兄弟节点，child及其孩子节点往下的树成员全部失联
        child->parent = NULL;                 //child父节点指针置空
        child->nextsibling = NULL;            //child兄弟点指针置空
        return;
    }
    while(cur->nextsibling != NULL)//当cur的兄弟节点存在
    {
        if(cur->nextsibling == child)//当cur的兄弟节点 == child
        {
            cur->nextsibling = child->nextsibling;//cur兄弟节点指针指向child的兄弟节点，child及其孩子节点往下的树成员全部失联
            child->parent = NULL;      //child父节点指针置空
            child->nextsibling = NULL; //child兄弟点指针置空
            return;
        }
        cur = cur->nextsibling;//未找到child节点，cur往右递进，比较它的兄弟节点
    }
}

//释放
void FreeNode(LTNode* treeNode)
{
    if(treeNode == NULL)
    {
        return;
    }
    //方式一
    // LTNode* cur = treeNode->firstChild;//创建临时节点记录指针cur，指向treeNode的孩子节点
    // while(cur != NULL)
    // {
    //     LTNode* nextNode = cur->nextsibling;//创建临时节点记录指针nextNode，指向cur的兄弟节点
    //     FreeNode(cur);//释放cur
    //     cur = nextNode;//将cur更新指向cur的兄弟节点
    // }
    //方式二
    FreeNode(treeNode->firstChild);//要释放该节点，先释放它的孩子节点和兄弟节点
    FreeNode(treeNode->nextsibling);
    //
    free(treeNode);//释放该节点
}

//释放树
void FreeTree(LTree* tree)
{
    FreeNode(tree->root);//释放根节点
    tree->root = NULL;//树根节点指针置空
}

//遍历节点
void TravelTreeNode(LTNode* node, int deepth, void (*func)(ElementType))
{
    if(node == NULL)//节点不存在，返回上一层递归调用
        return;
    if(func != NULL)
        func(node->data);//回调函数func只遍历树节点，遍历到该树节点会发生什么操作，由调用着决定回调函数的具体实现
    TravelTreeNode(node->firstChild, deepth + 1, func);//接着遍历该节点的孩子节点和兄弟节点
    TravelTreeNode(node->nextsibling, deepth, func);
}


//遍历
void TravelTree(LTree* tree, void (*func)(ElementType))
{
    TravelTreeNode(tree->root, 0, func);//从根节点开始遍历
}


//
int GetNodeHeight(LTNode* treenode)
{
    if(treenode == NULL)//该节点为空，返回上一层递归调用,并将childHeighet赋值为0
        return 0;
    int height = 0;
    LTNode* cur = treenode->firstChild;//创建临时节点记录指针cur，指向treenode的孩子节点
    while(cur != NULL)
    {
        int childHeighet = GetNodeHeight(cur);//递归调用找cur孩子节点的高度
        height = height > childHeighet ? height : childHeighet;//更新该节点在比较每个树分支后的最高层数
        cur = cur->nextsibling;//比较完cur孩子节点分支后都不符合，继续比较cur兄弟节点，指针右移
    }
    return height + 1;//返回上层递归调用时，加上treenode节点本身的一层高度
}

//树高
int GetTreeHeight(LTree* tree)
{
    return GetNodeHeight(tree->root);//从根节点开始获取节点高度，即该树的高度
}

//
LTNode* FindNode(LTNode* node, ElementType element, int (*func)(ElementType, ElementType))
{
    if(node == NULL)//该节点为空，返回上一层递归调用
        return NULL;
    if(func != NULL && func(node->data, element) == true)//通过回调函数比较node->data == element，返回该节点
        return node;
    LTNode* childNode  = node->firstChild;//创建临时节点记录指针childNode，指向node的孩子节点
    LTNode* targetNode  = NULL;//创建临时节点记录指针targetNode，指向使node->data == element的node节点，用于返回结果
    while(childNode != NULL)//node->firstChild节点存在
    {
        targetNode = FindNode(childNode, element, func);//该节点不符，递归比较该节点的孩子节点
        if(targetNode != NULL)//如果返回的节点不为空，根据第二个if语句可知，找到符合条件的节点，
            return targetNode;//将targetNode层层往上返回，其值不变
        childNode = childNode->nextsibling;////比较完cur孩子节点分支后都不符合，继续比较cur兄弟节点，指针右移
    }

    // if((targetNode = FindNode(node->firstChild,element, func)) != NULL)
    //     return targetNode;
    // if((targetNode = FindNode(node->nextSibling,element, func)) != NULL)
    //     return targetNode;

    return targetNode;
}

//发现节点
LTNode* FindTreeNode(LTree* tree, ElementType element, int (*func)(ElementType, ElementType))
{
    return FindNode(tree->root, element, func);//从树根节点开始比较
}


